// 满足滑动窗口，要满足以下两个条件：1. 值足够大 2. 位置在窗口里面（所以有些又晚出界又比较大的元素，会导致前面又小又早出界的元素，永远成不了滑动窗口的最大值）
// 窗口里面满足递减关系，才有可能进行窗口的尝试
// 符合这样头部出去，尾端进来，并且递减的，可以抽象成单调队列
func maxSlidingWindow(nums []int, k int) []int {
	// 使用一个数组，模拟单调队列
	q := []int{}
	// 自定义一个push函数，用来实现单调的队列的元素push操作
	push := func(i int) {
		// 如果当前nums[i]破坏了单调队列的单调性，则需要把单调队列里面所有的元素，全部移除
		for len(q) > 0 && nums[i] >= nums[q[len(q)-1]] {
			q = q[:len(q)-1]
		}
		// 然后再插入队列
		q = append(q, i)
	}

	// 前K个，不要涉及到出界的问题，直接无脑放进行了（大不了全部递减，不会涉及到出界）
	for i := 0; i < k; i++ {
		push(i)
	}

	n := len(nums)
	// 由于是滑动窗口，ans的长度可以基于n和k计算出来的
	ans := make([]int, 1, n-k+1)
	// 先把第一个元素加入ans
	ans[0] = nums[q[0]]
	for i := k; i < n; i++ {
		// 继续放元素
		push(i)
		// 如果q[0]出界，则移除
		for q[0] <= i-k {
			q = q[1:]
		}
		// 由于是递减的，只需要去q[0]下标的即可
		ans = append(ans, nums[q[0]])
	}
	return ans
}